package com.lun.swordtowardoffer2.c10;

public class MapSum {

	static class TrieNode{
		public static final int ENGLISH_LOWER_LETTER_TOTAL_NUM = 'z' - 'a' + 1;
		public TrieNode[] children;
		public int value;
		
		public TrieNode() {
			children = new TrieNode[ENGLISH_LOWER_LETTER_TOTAL_NUM];
		}
	}
	
	private TrieNode root;

	public MapSum() {
		this.root = new TrieNode();
	}
	
	public void insert(String word, int value) {
		TrieNode node = root;
		for(int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) - 'a';
			if(node.children[index] == null) {
				node.children[index] = new TrieNode();
			}
			node = node.children[index];
		}
		node.value = value;
	}
	
	public int sum(String prefix) {
		TrieNode node = root;
		for(int i = 0; i < prefix.length(); i++) {
			int index = prefix.charAt(i) - 'a';
			if(node.children[index] == null) {
				return 0;
			}
			node = node.children[index];
		}
		return getSum(node);
	}

	private int getSum(TrieNode node) {
		if(node == null)
			return 0;
		
		int result = node.value;
		for(TrieNode tn : node.children) {
			result += getSum(tn);
		}
		return result;
	}
	
}
